| 1. | (a) | Write the postfix form of the following expression : |
| a && b || c || ! (e > f) (c-expression) | ||
| (b) | Write an expression tree of the following expressions: | |
| (a<b) && (b<c) || (c < d) | ||
| (c) | Write a C- function to count the number of nodes in a linked list. | |
| (d) | Define threaded Binary tree. Write an algorithm for inorder traversal of a threaded | |
| Binary tree. | ||
| (e) | Which of the following expressions is in infix equivalent of the prefix form | |
| + - * ^ ABCD | E |
F +GH BB*C - D + (E | F) /G + H AB*(C-D) + E | (F | (G+H)) AB * C - D + E | F| G +H AB * C - D + E | (F | (G + H)) |
||
| (f) | Construct a Binary tree whose nodes in two orders are as under : | |
| Preorder : A B C D F
H J M K E G I L N Inorder : A D J M H K F C I N L G E B |
||
| 2 | (a) | Give a Binary tree representation of the following forest. |
 |
||
| (b) | Write down the order of nodes in preorder traversal of the above binary tree. | |
| (c) | Write an algorithm for preorder traversal of a Binary tree. | |
| 3. | (a) | Assume that we always access a certain file sequentially. Under what conditions, if any, is it advantageous to have the file organized sequential file rather than the sequential file ? |
| (b) | What are the important features of index sequential file organisation and random file | |
| organisation ? | ||
| (c) | Show the sequence of edges added by PRIM'S algorithm in constructing spanning | |
tree for the
following graph. |
||
| 4. | Write the following algorithm for a binary search tree : | |
| (a) | Recursive search of a node | |
| (b) | Deletion of a node (recursive) | |
| 5. | Give a brief comparison of Heap Sort and Quick Sort techniques. Write an | |
| algorithm to implement Heap Sort and discuss about its efficiency. | ||
| 6. | (a) | Thread the following binary tree into preorder and postorder. |
 |
||
| (b) | Write an algorithm to delete a node from a double linked circular list. |